/**
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
示例 2：

输入：n = 1, k = 1
输出：[[1]]
 

提示：

1 <= n <= 20
1 <= k <= n
 */

/**
 * 回溯套用公式代码：
void backtracking(参数){
	if(终止条件){
		存放结果；
		return；	
	}

	//横向遍历
	for（选择 ： 本层集合中的元素（书中节点孩子的数量就是集合的大小））｛
		处理节点；
		backtracking(路径，选择列表);	//纵向递归
		回溯，撤销处理结果。
	｝
}
 * 
 */

(function () {
    /**
     * @description 套用回溯公式
     * @param n
     * @param k
     * @returns
     */
    function combine(n: number, k: number): number[][] {
        if (k === n) {
            let ret = [];
            for (let i = 1; i <= n; i++) {
                ret.push(i);
            }
            return [ret];
        }
        const res: number[][] = [];
        const path: number[] = [];
        dfs(n, k, 1, path, res);
        return res;
    }

    function dfs(
        n: number,
        k: number,
        pos: number,
        path: number[],
        res: number[][]
    ) {
        if (path.length === k) {
            // console.log("path: %s", path);
            res.push([...path]);
            return;
        }

        for (let i = pos; i <= n; i++) {
            path.push(i);
            // console.log("path.push: %s", path);
            dfs(n, k, i + 1, path, res);
            path.pop();
        }
    }
})();
